Network delay time [DFS, Dijkstra’s algorithm (Heap)]¶
Time: O(ExLogV); Space: O(E); medium
There are N network nodes, labelled 1 to N.
Given times, a list of travel times as directed edges times[i] = (u, v, w), where:
u is the source node,
v is the target node, and
w is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K.
How long will it take for all nodes to receive the signal?
If it is impossible, return -1.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
Notes:
N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.
Hints:
We visit each node at some time, and if that time is better than the fastest time we’ve reached this node, we travel along outgoing edges in sorted order.
Alternatively, we could use Dijkstra’s algorithm.
1. Depth-First Search¶
Intuition
Let’s record the time dist[node] when the signal reaches the node.
If some signal arrived earlier, we don’t need to broadcast it anymore.
Otherwise, we should broadcast the signal.
Algorithm
We’ll maintain dist[node], the earliest that we arrived at each node.
When visiting a node while elapsed time has elapsed, if this is the currently-fastest signal at this node, let’s broadcast signals from this node.
To speed things up, at each visited node we’ll consider signals exiting the node that are faster first, by sorting the edges.
[2]:
import collections
class Solution1(object):
"""
Time: O(N^N + ELogE), where E is the length of times. We can only fully visit each node up to N−1 times,
one per each other node. Plus, we have to explore every edge and sort them.
Sorting each small bucket of outgoing edges is bounded by sorting all of them,
because of repeated use of the inequality x*log(x) + y*log(y) <= (x+y)*log(x+y).
Space: O(N + E), the size of the graph (O(E)), plus the size of the implicit call stack in our DFS (O(N)).
"""
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
graph = collections.defaultdict(list)
for u, v, w in times:
graph[u].append((w, v))
dist = {node: float('inf') for node in range(1, N+1)}
def dfs(node, elapsed):
if elapsed >= dist[node]: return
dist[node] = elapsed
for time, nei in sorted(graph[node]):
dfs(nei, elapsed + time)
dfs(K, 0)
ans = max(dist.values())
return ans if ans < float('inf') else -1
[3]:
s = Solution1()
times = [
[2,1,1],
[2,3,1],
[3,4,1]
]
N = 4
K = 2
assert s.networkDelayTime(times, N, K) == 2
2. Dijkstra’s Algorithm¶
Intuition and Algorithm
We use Dijkstra’s algorithm to find the shortest path from our source to all targets.
This is a textbook algorithm, refer to this link for more details.
Dijkstra’s algorithm is based on repeatedly making the candidate move that has the least distance travelled.
In our implementations below, we showcase both O(N^2) (basic) and O(NlogN) (heap) approaches.
[6]:
import collections
class Solution2(object):
"""
Dijkstra's Algorithm.
"""
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
graph = collections.defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {node: float('inf') for node in range(1, N+1)}
seen = [False] * (N+1)
dist[K] = 0
while True:
cand_node = -1
cand_dist = float('inf')
for i in range(1, N+1):
if not seen[i] and dist[i] < cand_dist:
cand_dist = dist[i]
cand_node = i
if cand_node < 0: break
seen[cand_node] = True
for nei, d in graph[cand_node]:
dist[nei] = min(dist[nei], dist[cand_node] + d)
ans = max(dist.values())
return ans if ans < float('inf') else -1
[7]:
s = Solution2()
times = [
[2,1,1],
[2,3,1],
[3,4,1]
]
N = 4
K = 2
assert s.networkDelayTime(times, N, K) == 2
3. Dijkstra’s Algorithm. Heap implementation.¶
[8]:
import collections
import heapq
class Solution3(object):
"""
Dijkstra's algorithm. Heap implementation.
Time: O((|E|+|V|)*Log|V|) = O(|E|*Log|V|) by using binary heap,
if we can further to use Fibonacci heap, it would be O(|E|+|V|*Log|V|)
Space: O(|E|+|V|) = O(|E|)
"""
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
adj = [[] for _ in range(N)]
for u, v, w in times:
adj[u-1].append((v-1, w))
result = 0
lookup = set()
best = collections.defaultdict(lambda: float("inf"))
min_heap = [(0, K-1)]
while min_heap and len(lookup) != N:
result, u = heapq.heappop(min_heap)
lookup.add(u)
if best[u] < result:
continue
for v, w in adj[u]:
if v in lookup: continue
if result+w < best[v]:
best[v] = result + w
heapq.heappush(min_heap, (result + w, v))
return result if len(lookup) == N else -1
[9]:
s = Solution3()
times = [
[2,1,1],
[2,3,1],
[3,4,1]
]
N = 4
K = 2
assert s.networkDelayTime(times, N, K) == 2
[10]:
import collections
import heapq
class Solution3a(object):
"""
Time: O(N^2 + E) where E is the length of times in the basic implementation,
and O(ELogE) in the heap implementation, as potentially every edge gets added to the heap.
Space: O(N+E), the size of the graph (O(E)), plus the size of the other objects used (O(N)).
"""
def networkDelayTime(self, times, N, K):
"""
:type times: List[List[int]]
:type N: int
:type K: int
:rtype: int
"""
graph = collections.defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
pq = [(0, K)]
dist = {}
while pq:
d, node = heapq.heappop(pq)
if node in dist: continue
dist[node] = d
for nei, d2 in graph[node]:
if nei not in dist:
heapq.heappush(pq, (d+d2, nei))
return max(dist.values()) if len(dist) == N else -1
[11]:
s = Solution3a()
times = [
[2,1,1],
[2,3,1],
[3,4,1]
]
N = 4
K = 2
assert s.networkDelayTime(times, N, K) == 2